package com.example.utils.util.TreeNodeUtil.utils;

import java.util.*;

/**
 * @Description     N叉树的遍历（Java版）先序、后序、层次遍历
 * @ClassName NaryTreeNode
 * @Author jiang_11445266119198
 * @Date 2022/11/20 12:58
 */
public class NaryTreeNode {

    private int val;
    private List<NaryTreeNode> children;

    public NaryTreeNode(int val) {
        this.val = val;
        children = new ArrayList<NaryTreeNode>();
    }

    public NaryTreeNode(int val, List<NaryTreeNode> children) {
        this.val = val;
        if (children != null) this.children = children;
        else this.children = new ArrayList<NaryTreeNode>();
    }

    public int getVal() {
        return val;
    }

    public List<NaryTreeNode> getChildren() {
        return children;
    }

    public boolean isLeaf() {
        if (children.isEmpty())
            return true;
        return false;
    }

    public boolean addChildNode(NaryTreeNode node) {
        children.add(node);
        return true;
    }

    /**
     * 先序遍历：根左右
     * 利用栈模拟递归调用
     * 将根结点压入栈中，当栈不空时执行：
     * 弹出栈中结点，将其放入结果队列中
     * 将该结点的孩子按照倒序依次放入栈中
     */
    public List<Integer> preOrder() {
        Stack<NaryTreeNode> stack = new Stack<>();
        LinkedList<Integer> pre = new LinkedList<>();
        if (this == null) return pre;
        stack.add(this);
        while (!stack.isEmpty()) {
            NaryTreeNode node = stack.pop();
            pre.add(node.val);
            Stack<NaryTreeNode> reChildren = new Stack<>();
            reChildren.addAll(node.children);
            while (!reChildren.isEmpty()) {
                stack.push(reChildren.pop());
            }

        }
        return pre;
    }

    /**
     * 后序遍历：左右根
     * 利用栈模拟递归调用
     * 将根结点压入栈中，当栈不空时执行：
     * 弹出栈中结点，将其头插放入结果队列中
     * 将该结点的孩子依次放入栈中
     */
    public List<Integer> postOrder() {
        Stack<NaryTreeNode> stack = new Stack<>();
        LinkedList post = new LinkedList();
        if (this == null) return post;
        stack.add(this);
        while (!stack.isEmpty()) {
            NaryTreeNode node = stack.pop();
            post.addFirst(node.val);
            stack.addAll(node.children);
        }
        return post;
    }

    /**
     * 层次遍历：
     * 利用队列模拟递归调用
     * 将根结点压入队中，当队不空时执行：
     * 获取当前队列长度，当迭代次数小于当前队列长度时：
     * 弹出当前队头结点，将其放入当前层的结果队列中
     * 将该结点的孩子依次放入队列中
     * 将当前层的结果队列放入结果队列中
     */
    public List<List<Integer>> levelOrder() {
        List<List<Integer>> result = new ArrayList<>();
        if (this == null) return result;
        Queue<NaryTreeNode> queue = new LinkedList<>();
        queue.add(this);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                NaryTreeNode node = queue.poll();
                level.add(node.val);
                queue.addAll(node.children);
            }
            result.add(level);
        }
        return result;
    }

}
